 #define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    string path;
    vector<string> ret;

    vector<string> letterCasePermutation(string s) {
        dfs(s, 0);
        return ret;
    }

    void dfs(string s, int pos)
    {
        if (pos == s.size())
        {
            ret.push_back(path);
            return;
        }

        char ch = s[pos];

        //不变
        path.push_back(ch);
        dfs(s, pos + 1);
        path.pop_back();


        //变
        if (ch < '0' || ch > '9')
        {
            char tmp = change(ch);
            path.push_back(tmp);
            dfs(s, pos + 1);
            path.pop_back();
        }
    }

    char change(char ch)
    {
        if (ch >= 'a' && ch <= 'z') ch -= 32;
        else ch += 32;
        return ch;
    }
};

class Solution {
public:
    bool check[16];
    int count;
    int countArrangement(int n) {
        dfs(1, n);
        return count;
    }

    void dfs(int pos, int n)
    {
        if (pos == n + 1)
        {
            count++;
            return;
        }

        for (int i = pos; i <= n; i++)
        {
            if (!check[i] || (i % pos == 0 || pos % i == 0))
            {
                check[i] = true;
                dfs(pos + 1, n);
                check[i] = false;//恢复现场
            }
        }
    }
};

class Solution {
public:
    vector<string> path;
    vector<vector<string>> ret;
    bool checkCol[10], checkDig1[20], checkDig2[20];
    int n;

    vector<vector<string>> solveNQueens(int _n) {
        n = _n;
        path.resize(n);
        for (int i = 0; i < n; i++)
            path[i].append(n, '.');

        dfs(0);
        return ret;
    }

    void dfs(int row)
    {
        if (row == n)
        {
            ret.push_back(path);
            return;
        }

        for (int col = 0; col < n; col++)//尝试在这一行放皇后
        {
            //剪枝
            if (!checkCol[col] && !checkDig1[row - col + n] && !checkDig2[row + col])
            {
                path[row][col] = 'Q';
                checkCol[col] = checkDig1[row - col + n] = checkDig2[row + col] = true;
                dfs(row + 1);

                //恢复现场
                path[row][col] = '.';
                checkCol[col] = checkDig1[row - col + n] = checkDig2[row + col] = false;
            }
        }
    }
};

class Solution {
public:
    //记录每个数是否出现
    bool row[9][10];
    bool col[9][10];
    bool grid[3][3][10];

    bool isValidSudoku(vector<vector<char>>& board) {
        for (int i = 0; i < 9; i++)
            for (int j = 0; j < 9; j++)
            {
                if (board[i][j] != '.')
                {
                    int num = board[i][j] - '0';
                    if (row[i][num] || col[j][num] || grid[i / 3][j / 3][num])
                        return false;
                    row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true;
                }

            }

        return true;
    }
};